#leetcode题目44：通配符匹配
#难度：困难
#时间复杂度：O(n^2)
#空间复杂度：O(1)

#方法：动态规划

from typing import List
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not s:
            return not p
        if not p:
            return False
        m,n=len(s),len(p)
        dp=[[False]*(n+1) for _ in range(m+1)]
        dp[0][0]=True
        for j in range(1,n+1):
            if p[j-1]=='*':
                dp[0][j]=True
            else:
                break
        for i in range(1,m+1):
            for j in range(1,n+1):
                if p[j-1]=='*':
                    dp[i][j]=dp[i-1][j] | dp[i][j-1]#这里的竖杠是或的意思
                elif p[j-1]=='? ' or p[j-1]==s[i-1]:
                    dp[i][j]=dp[i-1][j-1] 

        return dp[m][n]

#测试数据
s="aa"
p="a"
#预期输出：False
solution=Solution()
print(solution.isMatch(s,p))

s="aa"
p="*"
#预期输出：True
solution=Solution()
print(solution.isMatch(s,p))

s="cb"      
p="?a"
#预期输出：False
solution=Solution()
print(solution.isMatch(s,p))
